package com.leetcode.search.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/7/27 18:41
 */
public class CombinationSum2_40 {

    private int[] candidates;
    private final List<List<Integer>> res = new ArrayList<>();
    private boolean[] visited;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return res;
        Arrays.sort(candidates);
        this.candidates = candidates;
        visited = new boolean[candidates.length];
        backtrack(new LinkedList<>(), target, 0);
        return res;
    }

    private void backtrack(LinkedList<Integer> track, int target, int start) {
        if (0 == target) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            // 剪枝！！！！！！！！！！！！！！！！！！！！！！！！！
            // 相等并且访问过，那么就跳过
            // 这个条件是防止重复的模板条件！！

            // 首先确定大于0，保证跳过第一个数。并且前一个还没有
            if (i > 0 && candidates[i] == candidates[i - 1] && !visited[i - 1])
                continue;
            if (candidates[i] > target)
                break;
            visited[i] = true;
            track.offer(candidates[i]);
            backtrack(track, target - candidates[i], i + 1);
            visited[i] = false;
            track.removeLast();
        }
    }

}
